import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

    public static String nextLine() throws IOException {
        return br.readLine();
    }

    public static boolean hasNext() throws IOException {
        return br.ready();
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static int n,m;
    static int[] dis;
    static int[][] g;
    static boolean[] is;
    static int[] h,w,e,ne;  // 接表的存储
    static int idx;




    /**
     *朴素的dijkstra初始化
     *
     */
    private static void dijkstra(){
        Arrays.fill(dis,0x3f3f3f3f);
        dis[1]=0;

        for(int i=0;i<n;i++){

            int t=-1;

            for(int j=1;j<=n;j++){
                if(!is[j]&&(t==-1||dis[t]>dis[j])){
                    t=j;
                }
            }

            is[t]=true;
            for(int k=1;k<=n;k++){
                dis[k]=Math.min(dis[k],dis[t]+g[t][k] );
            }
        }


    }


    /**
     * 堆优化的dijkstra
     */

    private static void dijkstra1(){
        Arrays.fill(dis,0x3f3f3f3f);
        dis[1]=0;

        PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->a[0]-b[0]);
        q.offer(new int[]{0,1});

        while (!q.isEmpty()) {

            int[] arr = q.poll();

            int ver = arr[1];

            if(is[ver]) continue;
            int distance = arr[0];

            is[ver] = true;
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dis[j] > distance + w[i]) {
                    dis[j] = distance + w[i];
                    q.offer(new int[]{dis[j], j});
                }


            }
        }

    }

    /**
     * forn算法
     */

    static int[][] edges;

    private static void forn(){

        int k=2;   //限制边数为k条，得复制

        Arrays.fill(dis,0x3f3f3f3f);
        dis[1]=0;

        for(int i=0;i<k;i++){   //这里n改成k
            int[] copy = Arrays.copyOf(dis, dis.length);   //这里是复制dis，限制边数才用复制
            for(int j=0;j<m;j++){
                int a=edges[j][0];
                int b=edges[j][1];
                int c=edges[j][2];


                dis[b]=Math.min(dis[b], c+copy[a]);

            }
        }


    }


    /**
     * spfa算法
     */


    static int[] cn;
    static boolean spfa(){
        cn=new int[n+1];

        Arrays.fill(dis,0x3f3f3f3f);


      Queue<Integer> q=new LinkedList<>();

      for(int i=1;i<=n;i++){
          q.add(i);
          is[i]=true;
      }

      while (!q.isEmpty()){

          int ver=q.poll();
          dis[1]=0;

          is[ver]=false;

          for(int i=h[ver];i!=-1;i=ne[i]){

              int j=e[i];
              if(dis[j]>dis[ver]+w[i]){
                  dis[j]=dis[ver]+w[i];

                  cn[j]=cn[ver]+1;   //边数加1
                  if(cn[j]>=n) return true;   //如果大于n则存在负环

                  if(!is[j]){

                      q.add(j);
                      is[j]=true;
                  }
              }
          }
      }

      return false;

    }






    private static void add(int a,int b,int weigth){
        w[idx]=weigth;e[idx]=b;ne[idx]=h[a];h[a]=idx++;
    }



    public static void main(String[] args) throws IOException {
        n=nextInt();
        m=nextInt();

        dis=new int[n+1];





        h=new int[n+1];    //堆优化的dijkstra初始化，里面必需确定边的数量有多少
        w=new int[m+1];
        e=new int[m+1];
        ne=new int[m+1];
        Arrays.fill(h,-1);





        g=new int[n+1][n+1];   //朴素的dijkstra初始化
        is=new boolean[n+1];


        edges=new int[m+1][3];  //初始化forn数组








        for(int i=0;i<=n;i++) Arrays.fill(g[i],0x3f3f3f3f);

        for (int i = 0; i < m; i++) {


            int a=nextInt();
            int b=nextInt();
            int c=nextInt();

            g[a][b]=Math.min(c,g[a][b]);  ////朴素的dijkstra初始化

            add(a,b,c);//堆优化的dijkstra初始化，

            edges[i][0]=a;
            edges[i][1]=b;
            edges[i][2]=c;



        }

//        System.out.println(spfa());

        forn();

        for (int i:dis) System.out.println(i);



    }
}
